/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-16
 * Time: 9:06
 */
class Trie{
    // arr[0] != null , 表示这一 bit 位 有 0
    public Trie[] arr;
    public Trie(){
        this.arr = new Trie[2];
    }
}

public class Solution {
    public Trie root = new Trie();
    public int findMaximumXOR(int[] nums) {
        int max = 0;
        for (int x: nums) {
            Trie cur = this.root;
            // 记录这个数与其他数异或的最大值
            int temp = 0;
            for (int i = 31; i >= 0; i--) {
                // 先把这个数字放到前缀树里面
                int value = (x >> i) & 1; // 这一 bit 位, 为 0 / 1
                if (cur.arr[value] == null){
                    cur.arr[value] = new Trie();
                }
                cur = cur.arr[value];

                // 开始找 异或最大的

                // 记录与哪个节点进行比较
                Trie cmp = this.root;
                // 如果本位 为 1, 那么应该最先考虑本位为 0的, 反之亦然
                // 这样才能使得异或结果尽可能大
                if (value == 1){
                    if (cmp.arr[0] != null){
                        temp += (1 << i);
                        cmp = cmp.arr[0];
                    }else{
                        cmp = cmp.arr[1];
                    }
                }else{
                    if (cmp.arr[1] != null){
                        temp += (1 << i);
                        cmp = cmp.arr[1];
                    }else{
                        cmp = cmp.arr[0];
                    }
                }
            }
            max = Math.max(max, temp);
        }
        return max;
    }
}
